home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 3 / Info_Mac_1994-01.iso / Development / Source / MacGzip 0.1b2 Source / gzip-1.2.4 sources / unlzh.c < prev    next >
Text File  |  1993-11-08  |  9KB  |  408 lines
  1. /* unlzh.c -- decompress files in SCO compress -H (LZH) format.
  2.  * The code in this file is directly derived from the public domain 'ar002'
  3.  * written by Haruhiko Okumura.
  4.  */
  5.  
  6. /*
  7.  * Modified:1993 by SPDsoft for MacGzip
  8.  *
  9.  */
  10.  
  11.  
  12. #ifdef RCSID
  13. static char rcsid[] = "$Id: unlzh.c,v 1.2 1993/06/24 10:59:01 jloup Exp $";
  14. #endif
  15.  
  16. #include <stdio.h>
  17.  
  18. #include "tailor.h"
  19. #include "gzip.h"
  20. #include "lzw.h" /* just for consistency checking */
  21.  
  22. /* decode.c */
  23.  
  24. local unsigned  decode  OF((unsigned count, uch buffer[]));
  25. local void decode_start OF((void));
  26.  
  27. /* huf.c */
  28. local void huf_decode_start OF((void));
  29. local unsigned decode_c     OF((void));
  30. local unsigned decode_p     OF((void));
  31. local void read_pt_len      OF((int nn, int nbit, int i_special));
  32. local void read_c_len       OF((void));
  33.  
  34. /* io.c */
  35. local void fillbuf      OF((int n));
  36. local unsigned getbits  OF((int n));
  37. local void init_getbits OF((void));
  38.  
  39. /* maketbl.c */
  40.  
  41. local void make_table OF((int nchar, uch bitlen[],
  42.               int tablebits, ush table[]));
  43.  
  44.  
  45. #define DICBIT    13    /* 12(-lh4-) or 13(-lh5-) */
  46. #define DICSIZ ((unsigned) 1 << DICBIT)
  47.  
  48. #ifndef CHAR_BIT
  49. #  define CHAR_BIT 8
  50. #endif
  51.  
  52. #ifndef UCHAR_MAX
  53. #  define UCHAR_MAX 255
  54. #endif
  55.  
  56. #define BITBUFSIZ (CHAR_BIT * 2 * sizeof(char))
  57. /* Do not use CHAR_BIT * sizeof(bitbuf), does not work on machines
  58.  * for which short is not on 16 bits (Cray).
  59.  */
  60.  
  61. /* encode.c and decode.c */
  62.  
  63. #define MAXMATCH 256    /* formerly F (not more than UCHAR_MAX + 1) */
  64. #define THRESHOLD  3    /* choose optimal value */
  65.  
  66. /* huf.c */
  67.  
  68. #define NC (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD)
  69.     /* alphabet = {0, 1, 2, ..., NC - 1} */
  70. #define CBIT 9  /* $\lfloor \log_2 NC \rfloor + 1$ */
  71. #define CODE_BIT  16  /* codeword length */
  72.  
  73. #define NP (DICBIT + 1)
  74. #define NT (CODE_BIT + 3)
  75. #define PBIT 4  /* smallest integer such that (1U << PBIT) > NP */
  76. #define TBIT 5  /* smallest integer such that (1U << TBIT) > NT */
  77. #if NT > NP
  78. # define NPT NT
  79. #else
  80. # define NPT NP
  81. #endif
  82.  
  83. /* local ush left[2 * NC - 1]; */
  84. /* local ush right[2 * NC - 1]; */
  85. #define left  prev
  86. #define right head
  87. #if NC > (1<<(BITS-2))
  88.     error cannot overlay left+right and prev
  89. #endif
  90.  
  91. /* local uch c_len[NC]; */
  92. #define c_len outbuf
  93. #if NC > OUTBUFSIZ
  94.     error cannot overlay c_len and outbuf
  95. #endif
  96.  
  97. local uch pt_len[NPT];
  98. local unsigned blocksize;
  99. local ush pt_table[256];
  100.  
  101. /* local ush c_table[4096]; */
  102. #define c_table d_buf
  103. #if (DIST_BUFSIZE-1) < 4095
  104.     error cannot overlay c_table and d_buf
  105. #endif
  106.  
  107. /***********************************************************
  108.         io.c -- input/output
  109. ***********************************************************/
  110.  
  111. local ush       bitbuf;
  112. local unsigned  subbitbuf;
  113. local int       bitcount;
  114.  
  115. local void fillbuf(n)  /* Shift bitbuf n bits left, read n bits */
  116.     int n;
  117. {
  118.     bitbuf <<= n;
  119.     while (n > bitcount) {
  120.     bitbuf |= subbitbuf << (n -= bitcount);
  121.     subbitbuf = (unsigned)try_byte();
  122.     if ((int)subbitbuf == EOF) subbitbuf = 0;
  123.     bitcount = CHAR_BIT;
  124.     }
  125.     bitbuf |= subbitbuf >> (bitcount -= n);
  126. }
  127.  
  128. local unsigned getbits(n)
  129.     int n;
  130. {
  131.     unsigned x;
  132.  
  133.     x = bitbuf >> (BITBUFSIZ - n);  fillbuf(n);
  134.     return x;
  135. }
  136.  
  137. local void init_getbits()
  138. {
  139.     bitbuf = 0;  subbitbuf = 0;  bitcount = 0;
  140.     fillbuf(BITBUFSIZ);
  141. }
  142.  
  143. /***********************************************************
  144.     maketbl.c -- make table for decoding
  145. ***********************************************************/
  146.  
  147. local void make_table(nchar, bitlen, tablebits, table)
  148.     int nchar;
  149.     uch bitlen[];
  150.     int tablebits;
  151.     ush table[];
  152. {
  153.     ush count[17], weight[17], start[18], *p;
  154.     unsigned i, k, len, ch, jutbits, avail, nextcode, mask;
  155.  
  156.     for (i = 1; i <= 16; i++) count[i] = 0;
  157.     for (i = 0; i < (unsigned)nchar; i++) count[bitlen[i]]++;
  158.  
  159.     start[1] = 0;
  160.     for (i = 1; i <= 16; i++)
  161.     start[i + 1] = start[i] + (count[i] << (16 - i));
  162.     if ((start[17] & 0xffff) != 0)
  163.     error("Bad table\n");
  164.  
  165.     jutbits = 16 - tablebits;
  166.     for (i = 1; i <= (unsigned)tablebits; i++) {
  167.     start[i] >>= jutbits;
  168.     weight[i] = (unsigned) 1 << (tablebits - i);
  169.     }
  170.     while (i <= 16) {
  171.     weight[i] = (unsigned) 1 << (16 - i);
  172.     i++;
  173.     }
  174.  
  175.     i = start[tablebits + 1] >> jutbits;
  176.     if (i != 0) {
  177.     k = 1 << tablebits;
  178.     while (i != k) table[i++] = 0;
  179.     }
  180.  
  181.     avail = nchar;
  182.     mask = (unsigned) 1 << (15 - tablebits);
  183.     for (ch = 0; ch < (unsigned)nchar; ch++) {
  184.     if ((len = bitlen[ch]) == 0) continue;
  185.     nextcode = start[len] + weight[len];
  186.     if (len <= (unsigned)tablebits) {
  187.         for (i = start[len]; i < nextcode; i++) table[i] = ch;
  188.     } else {
  189.         k = start[len];
  190.         p = &table[k >> jutbits];
  191.         i = len - tablebits;
  192.         while (i != 0) {
  193.         if (*p == 0) {
  194.             right[avail] = left[avail] = 0;
  195.             *p = avail++;
  196.         }
  197.         if (k & mask) p = &right[*p];
  198.         else          p = &left[*p];
  199.         k <<= 1;  i--;
  200.         }
  201.         *p = ch;
  202.     }
  203.     start[len] = nextcode;
  204.     }
  205. }
  206.  
  207. /***********************************************************
  208.         huf.c -- static Huffman
  209. ***********************************************************/
  210.  
  211. local void read_pt_len(nn, nbit, i_special)
  212.     int nn;
  213.     int nbit;
  214.     int i_special;
  215. {
  216.     int i, c, n;
  217.     unsigned mask;
  218.  
  219.     n = getbits(nbit);
  220.     if (n == 0) {
  221.     c = getbits(nbit);
  222.     for (i = 0; i < nn; i++) pt_len[i] = 0;
  223.     for (i = 0; i < 256; i++) pt_table[i] = c;
  224.     } else {
  225.     i = 0;
  226.     while (i < n) {
  227.         c = bitbuf >> (BITBUFSIZ - 3);
  228.         if (c == 7) {
  229.         mask = (unsigned) 1 << (BITBUFSIZ - 1 - 3);
  230.         while (mask & bitbuf) {  mask >>= 1;  c++;  }
  231.         }
  232.         fillbuf((c < 7) ? 3 : c - 3);
  233.         pt_len[i++] = c;
  234.         if (i == i_special) {
  235.         c = getbits(2);
  236.         while (--c >= 0) pt_len[i++] = 0;
  237.         }
  238.     }
  239.     while (i < nn) pt_len[i++] = 0;
  240.     make_table(nn, pt_len, 8, pt_table);
  241.     }
  242. }
  243.  
  244. local void read_c_len()
  245. {
  246.     int i, c, n;
  247.     unsigned mask;
  248.  
  249.     n = getbits(CBIT);
  250.     if (n == 0) {
  251.     c = getbits(CBIT);
  252.     for (i = 0; i < NC; i++) c_len[i] = 0;
  253.     for (i = 0; i < 4096; i++) c_table[i] = c;
  254.     } else {
  255.     i = 0;
  256.     while (i < n) {
  257.         c = pt_table[bitbuf >> (BITBUFSIZ - 8)];
  258.         if (c >= NT) {
  259.         mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
  260.         do {
  261.             if (bitbuf & mask) c = right[c];
  262.             else               c = left [c];
  263.             mask >>= 1;
  264.         } while (c >= NT);
  265.         }
  266.         fillbuf((int) pt_len[c]);
  267.         if (c <= 2) {
  268.         if      (c == 0) c = 1;
  269.         else if (c == 1) c = getbits(4) + 3;
  270.         else             c = getbits(CBIT) + 20;
  271.         while (--c >= 0) c_len[i++] = 0;
  272.         } else c_len[i++] = c - 2;
  273.     }
  274.     while (i < NC) c_len[i++] = 0;
  275.     make_table(NC, c_len, 12, c_table);
  276.     }
  277. }
  278.  
  279. local unsigned decode_c()
  280. {
  281.     unsigned j, mask;
  282.  
  283.     if (blocksize == 0) {
  284.     blocksize = getbits(16);
  285.     if (blocksize == 0) {
  286.         return NC; /* end of file */
  287.     }
  288.     read_pt_len(NT, TBIT, 3);
  289.     read_c_len();
  290.     read_pt_len(NP, PBIT, -1);
  291.     }
  292.     blocksize--;
  293.     j = c_table[bitbuf >> (BITBUFSIZ - 12)];
  294.     if (j >= NC) {
  295.     mask = (unsigned) 1 << (BITBUFSIZ - 1 - 12);
  296.     do {
  297.         if (bitbuf & mask) j = right[j];
  298.         else               j = left [j];
  299.         mask >>= 1;
  300.     } while (j >= NC);
  301.     }
  302.     fillbuf((int) c_len[j]);
  303.     return j;
  304. }
  305.  
  306. local unsigned decode_p()
  307. {
  308.     unsigned j, mask;
  309.  
  310.     j = pt_table[bitbuf >> (BITBUFSIZ - 8)];
  311.     if (j >= NP) {
  312.     mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
  313.     do {
  314.         if (bitbuf & mask) j = right[j];
  315.         else               j = left [j];
  316.         mask >>= 1;
  317.     } while (j >= NP);
  318.     }
  319.     fillbuf((int) pt_len[j]);
  320.     if (j != 0) j = ((unsigned) 1 << (j - 1)) + getbits((int) (j - 1));
  321.     return j;
  322. }
  323.  
  324. local void huf_decode_start()
  325. {
  326.     init_getbits();  blocksize = 0;
  327. }
  328.  
  329. /***********************************************************
  330.         decode.c
  331. ***********************************************************/
  332.  
  333. local int j;    /* remaining bytes to copy */
  334. local int done; /* set at end of input */
  335.  
  336. local void decode_start()
  337. {
  338.     huf_decode_start();
  339.     j = 0;
  340.     done = 0;
  341. }
  342.  
  343. /* Decode the input and return the number of decoded bytes put in buffer
  344.  */
  345. local unsigned decode(count, buffer)
  346.     unsigned count;
  347.     uch buffer[];
  348.     /* The calling function must keep the number of
  349.        bytes to be processed.  This function decodes
  350.        either 'count' bytes or 'DICSIZ' bytes, whichever
  351.        is smaller, into the array 'buffer[]' of size
  352.        'DICSIZ' or more.
  353.        Call decode_start() once for each new file
  354.        before calling this function.
  355.      */
  356. {
  357.     local unsigned i;
  358.     unsigned r, c;
  359.  
  360.     r = 0;
  361.     while (--j >= 0) {
  362.     buffer[r] = buffer[i];
  363.     i = (i + 1) & (DICSIZ - 1);
  364.     if (++r == count) return r;
  365.     }
  366.     for ( ; ; ) {
  367.     c = decode_c();
  368.     if (c == NC) {
  369.         done = 1;
  370.         return r;
  371.     }
  372.     if (c <= UCHAR_MAX) {
  373.         buffer[r] = c;
  374.         if (++r == count) return r;
  375.     } else {
  376.         j = c - (UCHAR_MAX + 1 - THRESHOLD);
  377.         i = (r - decode_p() - 1) & (DICSIZ - 1);
  378.         while (--j >= 0) {
  379.         buffer[r] = buffer[i];
  380.         i = (i + 1) & (DICSIZ - 1);
  381.         if (++r == count) return r;
  382.         }
  383.     }
  384.     }
  385. }
  386.  
  387.  
  388. /* ===========================================================================
  389.  * Unlzh in to out. Return OK or ERROR.
  390.  */
  391. int unlzh(in, out)
  392.     int in;
  393.     int out;
  394. {
  395.     unsigned n;
  396.     ifd = in;
  397.     ofd = out;
  398.  
  399.     decode_start();
  400.     while (!done) {
  401.     n = decode((unsigned) DICSIZ, window);
  402.     if (!test && n > 0) {
  403.         write_buf(out, (char*)window, n);
  404.     }
  405.     }
  406.     return OK;
  407. }
  408.